package com.tgy.leetcode;

import java.util.Stack;

/**
 * @Author: tgy
 * @Date: 2020-11-04 11:55
 *
 * https://leetcode-cn.com/problems/trapping-rain-water/
 */
public class _42_接雨水_递减栈_04 {

    public int trap(int[] height) {

        if (height == null || height.length <= 2) {

            return 0;
        }


        int index;
        int sumWater = 0;

        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < height.length; i++) {

            if (stack.isEmpty() || height[stack.peek()] >= height[i]) {

                stack.push(i);
                continue;
            }

            while (!stack.isEmpty() && height[index = stack.peek()] < height[i]) {

                stack.pop();
                int preIndex;
                if (!stack.isEmpty() && (height[preIndex = stack.peek()] != height[index])) {

                    sumWater += (Math.min(height[preIndex], height[i]) - height[index]) * (i - preIndex - 1);
                }
            }

            stack.push(i);
        }

        return sumWater;
    }
}
